package Data_Structure.Sort;

import java.util.Stack;

/**
 * @className: QuickSort
 * @author: 芃
 * @description: 快排实现
 * @date: 2023/8/20 17:18
 */
//主要思想:
//①、找基准
//将arr[0]的值存储起来，定义start和end下标，分别从数组两端开始走
//将arr[0]下标的值作为参照，end遍历到比arr[0]小的位置就停下来
//将end下标的值放到start下标位置处
//将arr[0]下标的值作为参照，start遍历到比arr[0]大的位置就停下来
//将start下标的值放到end下标位置处
//当start和end相遇时，此时的下标就是arr[0]的值在排序后理应存在的位置
//将arr[0]的值放在该位置处，此时左边区间的值均小于这个值，右边区间的值均大于这个值
//②、分而治之
//上述步骤①只是将一个元素找到了它应该存放的位置
//递归它的左右区间，重复步骤①
//最后整个数组的元素就存放在了排序后理应存在的位置处

//时间复杂度：最好情况下-》每次可以均匀的分割待排序序列O(N*logN)
//最坏情况下-》数据有序或者逆序 O(N^2)
//空间复杂度：最好情况下 O(logN) 因为是递归，所以需要维护函数的调用关系，即调用层度
//对应的，最坏情况下，数据有序或者逆序，空间复杂度也会提升至O(N)
//稳定性：不稳定的
//综上所述：对于快排，数据越无序越快
public class QuickSort {
    //非递归形式-借助栈
    public static void quickSort2(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length - 1;
        int pivot = partition(arr,left,right);
        if (pivot > left + 1){
            //说明左边有两个元素
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(arr,left,right);
            if (pivot > left + 1){
                //说明左边有两个元素
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    private static int partition(int[] arr, int start, int end) {
        int tmp = arr[start];
        while (start < end){
            while (start < end && arr[end] >= tmp){
                end--;
            }
            //end下标就遇到了小于tmp的值
            //把end下标的值给start下标
            arr[start] = arr[end];
            while (start < end && arr[start] <= tmp){
                start++;
            }
            //start下标就遇到了大于tmp的值
            //把start下标的值给end
            arr[end] = arr[start];
        }
        //走到这，说明左右两侧检测完成，将tmp的值放到该在的下标
        arr[end] = tmp;
        return end;
    }

    //递归形式
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length - 1);
    }
    public static void quick(int[] arr,int left,int right){
        if (left >= right){
            return;
        }
        //优化：当数据逐渐趋于有序时，可以使用直接插入排序进行排序
        if (right - left+1 <= 10){
            //调用直接插入排序
            insertSort(arr,left,right);
            return;
        }
        //在找基准之前，我们找到中间大小的值-使用三数取中法
        int midValue = findMidValIndex(arr,left,right);
        int tmp = arr[midValue];
        arr[midValue] = arr[left];
        arr[left] = tmp;
        //找基准
        int pivot = findPivot(arr,left,right);
        //左边
        quick(arr,left,pivot-1);
        //右边
        quick(arr,pivot+1,right);
    }
    private static int findMidValIndex(int[] array,int start,int end){
        int mid = start + ((end - start) >>> 1);
        if (array[start] < array[end]){
            if (array[mid] < array[start]){
                return start;
            }else if (array[mid] > array[end]){
                return end;
            }else {
                return mid;
            }
        }else {
            if (array[mid] < array[end]){
                return end;
            }else if (array[mid] > array[start]){
                return start;
            }else {
                return mid;
            }
        }
    }
    public static int findPivot(int[] arr,int start,int end){
        int tmp = arr[start];
        while (start < end){
            while (start < end && arr[end] >= tmp){
                end--;
            }
            //end下标就遇到了小于tmp的值
            //把end下标的值给start下标
            arr[start] = arr[end];
            while (start < end && arr[start] <= tmp){
                start++;
            }
            //start下标就遇到了大于tmp的值
            //把start下标的值给end
            arr[end] = arr[start];
        }
        //走到这，说明左右两侧检测完成，将tmp的值放到该在的下标
        arr[end] = tmp;
        return end;
    }

    public static void insertSort(int[] arr,int start,int end){
        for (int i = start; i <= end; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= start; j--) {
                if (arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else {
                    //只要j回退的时候遇到了比tmp小的就结束比较，因为前面的顺序已经有序，只是在给tmp找合适的位置
                    //arr[j+1] = tmp;
                    break;
                }
            }
            //j回退到了小于0的下标
            arr[j+1] = tmp;
        }
    }
}
